One fundamental choice a developer makes when developing software is the selection of appropriate data structures to facilitate organizing and referencing data. Many different types of data structures are available, including linked lists, stacks, trees, arrays and others. Each data structure is associated with certain advantages and limitations.
One frequently-used data structure is the tree. One common form of tree is composed of a finite set of elements called nodes, linked together from a root to one or more internal nodes, each of which may be linked to one or more nodes, eventually ending in a number of leaf nodes. Typically, nodes closer to the root are parent nodes of the nodes farther away from the root. The nodes farther away from the root are called child nodes of the parent nodes. Data is typically stored in the nodes and can be referenced using the links from root to node to leaf and from parent to child and so on. Consequently, a hierarchical or sequential relationship may be attributed to data stored in the nodes of a tree structure. A hierarchical relationship can also be understood as a contextual relationship, each node being accessible within the context of its parent node.
One limitation of tree data structures is that typically, a tree can only represent one hierarchy. For example, a root node for sales activities could have a number of nodes depending from the root node, each node representing a particular salesman. Each salesman node could have child nodes, each salesman child node representing, for example, sales in a particular state. Hence, this tree could be easily accessed for state information within the context of salesman, that is, this tree could be used to efficiently answer the question: “What states does Salesman Bob sell in?”. If, instead of accessing state data by salesman, salesman data within the context of state were needed, (that is, we want to answer the question: “What salesmen sell in Texas?”), another tree would have to be created, with nodes representing states depending from the root salesman activity, from which child nodes representing salesmen might depend. The alternative to creating another tree would be to traverse the entire tree to extract the desired information.
It would be helpful if one structure could record all possible contextual relationships within the data, thereby achieving efficiencies not possible with a standard tree data structure.